function Node (key = 0, left = null, right = null) {
  this.key = key
  this.left = left
  this.right = right
}

/**
 * 主函数来着
 */
function BinarySearchTree(rootKey) {
  this.root = new Node(rootKey)
}


/**
 * 得到一个新的树节点
 * @param {any} key 
 * @returns Node
 */
 BinarySearchTree.prototype.getNewNode = function(key) {
  return new Node(key)
}


/**
 * 不起作用的一个函数
 * @param {Node} root 
 * @returns void
 */
 BinarySearchTree.prototype.clear = function(root) {
  if(root == null) return
  this.clear(root.left)
  this.clear(root.right)
  // delete root
  root = null
  return
}

/**
 * 树节点的插入操作
 * @param {node} root 
 * @param {any} key 
 * @returns node
 */
BinarySearchTree.prototype.insert = function(root, key) {
  if(root == null) return this.getNewNode(key)
  if(root.key == key) return root
  if(key < root.key) root.left = this.insert(root.left,key)
  else root.right = this.insert(root.right, key)
  return root
}
/**
 * 删除树的节点
 * @param {node} root 
 * @param {any} key
 */
BinarySearchTree.prototype.earse = function(root, key) {
  if(root == null) return root
  if(key < root.key) root.left = this.earse(root.left, key)
  else if(key > root.key) root.left = this.earse(root.right, key)
  else {
    if(root.left == null && root.right == null) {
      root = null
      return null
    } else if((root.left == null && root.right) || (root.left && root.right == null)) {
      let temp = root.left ? root.left : root.right
      root = null
      return temp
    } else {
      let temp = this.predeccessor(root)
      root.key = temp.key
      root.left = this.earse(root.left, temp.key)
      // console.log(root.left)
      // return 
    }
  }
  return root
}


/**
 * 找到前驱节点
 * @param {node} root 
 * @returns node
 */
BinarySearchTree.prototype.predeccessor = function(root) {
  let temp = root.left
  while(temp.right) temp = temp.right
  return temp
}


const temp = new BinarySearchTree(15)
temp.insert(temp.root, 14)
temp.insert(temp.root, 13)
temp.insert(temp.root, 10)
temp.insert(temp.root, 17)
temp.insert(temp.root, 12)
temp.insert(temp.root, 5)
temp.insert(temp.root, 16)
temp.insert(temp.root, 9)
temp.earse(temp.root,10)
console.log(JSON.stringify(temp.root, null, 2))